{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Convert Binary Number in a Linked List to Integer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getDecimalValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二进制链表转整数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个单链表的引用结点&nbsp;<code>head</code>。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。</p>\n",
    "\n",
    "<p>请你返回该链表所表示数字的 <strong>十进制值</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/12/15/graph-1.png\" style=\"height: 108px; width: 426px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>head = [1,0,1]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>二进制数 (101) 转化为十进制数 (5)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>head = [0]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>head = [1]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]\n",
    "<strong>输出：</strong>18880\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>head = [0,0]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表不为空。</li>\n",
    "\t<li>链表的结点总数不超过&nbsp;<code>30</code>。</li>\n",
    "\t<li>每个结点的值不是&nbsp;<code>0</code> 就是 <code>1</code>。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [convert-binary-number-in-a-linked-list-to-integer](https://leetcode.cn/problems/convert-binary-number-in-a-linked-list-to-integer/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [convert-binary-number-in-a-linked-list-to-integer](https://leetcode.cn/problems/convert-binary-number-in-a-linked-list-to-integer/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,1]', '[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        res = head.val\n",
    "        while head.next:\n",
    "            head = head.next\n",
    "            res = (res << 1) + head.val\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        if not head:\n",
    "            return 0\n",
    "        tmp = list()\n",
    "        while(head):\n",
    "            tmp.append(str(head.val))\n",
    "            head = head.next\n",
    "        \n",
    "        tmp = ''.join(tmp)\n",
    "        return int(tmp,2)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        ans = 0\n",
    "        cur = head\n",
    "        while cur:\n",
    "            ans = (ans << 1) + cur.val\n",
    "            cur = cur.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        result = 0\n",
    "        while head != None:\n",
    "            result = result *2 + head.val\n",
    "            head = head.next\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        re = 0\n",
    "        tmp = head\n",
    "        while tmp is not None:\n",
    "            re = (re << 1) | tmp.val\n",
    "            tmp = tmp.next\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        num = 0\n",
    "        mark = []\n",
    "        while head:\n",
    "            mark.append(head.val)\n",
    "            head = head.next\n",
    "        index = len(mark) - 1\n",
    "        for i in mark:\n",
    "            if i == 1:\n",
    "                num += 2 ** index\n",
    "            index -= 1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        result = 0\n",
    "        while head != None:\n",
    "            result = result*2 + head.val \n",
    "            head = head.next\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        p = head\n",
    "        num = []\n",
    "        a = 0\n",
    "        count = 0\n",
    "        while True:\n",
    "            count += 1\n",
    "            num.append(p.val)\n",
    "            if p.next is None:\n",
    "                break\n",
    "            p = p.next\n",
    "        \n",
    "        for i in range(count):\n",
    "            a += num[i] * (2**(count - i - 1))\n",
    "        \n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        cur = head\n",
    "        num = 0\n",
    "        while cur:\n",
    "            num = num * 2 + cur.val\n",
    "            cur = cur.next\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        sum_count = 0\n",
    "        #index = 0\n",
    "        new_list = []\n",
    "        while head:\n",
    "            #sum_count += head.val*pow(2,index)\n",
    "            new_list.append(head.val)\n",
    "            print(head.val)\n",
    "            head = head.next\n",
    "        for index,item in enumerate(new_list[-1::-1]):\n",
    "            print(index,item)\n",
    "            sum_count += item*pow(2,index)\n",
    "        return sum_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        ans = 0\n",
    "        cur = head\n",
    "        while cur is not None:\n",
    "            ans = ans * 2 + cur.val\n",
    "            cur = cur.next\n",
    "        return ans      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        cur = head\n",
    "        ans = 0\n",
    "        while cur:\n",
    "            ans = ans * 2 + cur.val\n",
    "            cur = cur.next\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        binstr = \"\"\n",
    "        while head:\n",
    "            binstr += str(head.val)\n",
    "            head = head.next\n",
    "        return int(binstr,2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        '''\n",
    "        res, i, n = 0, 0, 0\n",
    "        prev, curr = head, head\n",
    "        while prev:\n",
    "            n += 1\n",
    "            prev = prev.next\n",
    "        while curr:\n",
    "            res += curr.val * (2**(n-i-1))\n",
    "            i += 1\n",
    "            curr = curr.next\n",
    "        return res\n",
    "        '''\n",
    "        # 模拟法\n",
    "        res = 0\n",
    "        curr = head\n",
    "        while curr:\n",
    "            res = 2 * res + curr.val\n",
    "            curr = curr.next\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        cur = head\n",
    "        ans = 0\n",
    "        while cur:\n",
    "            ans = ans * 2 + cur.val\n",
    "            cur = cur.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        cur = head\n",
    "        ans = 0\n",
    "        while cur:\n",
    "            ans = ans * 2 + cur.val\n",
    "            cur = cur.next\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        result = ''\n",
    "        while head:\n",
    "            result = result + str(head.val)\n",
    "            head = head.next\n",
    "        return int(result, 2)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        res = ''\n",
    "        while head:\n",
    "            res += str(head.val)\n",
    "            head = head.next\n",
    "        return int(res,2)\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
